package cn.suchan.jianzhi.q33_uglynumber;

/**
 * 知识点：丑数
 * 题目描述
 * 把只包含质因子2、3和5的数称作丑数（Ugly Number）。
 * 例如6、8都是丑数，但14不是，因为它包含质因子7。
 * 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
 *
 * <p>
 * 判断方法：
 * 首先除以2，直到不能整除为止；
 * 然后除以5，直到不能整除为止；
 * 最后除以3，直到不能整除为止；
 * 如果最后的那个商为1,则为丑数，否则不是。
 * </p>
 *
 * @author suchan
 * @date 2019/05/31
 */
public class Solution {

    /**
     * 可以看出丑数的规律：
     * 第一个数是1，从第二个数开始，就是2/3/5的倍数中的最小值
     *
     * @param index
     * @return
     */
    public int GetUglyNumber_Solution(int index) {
        if (index <= 0) {
            return 0;
        }
        // 1、2=2*1、3=3*1、4=2*2、5=5*1、6=2*3(3*2)、8=2*4、9=3*3、10=2*5(5*2)、12=2*6(3*4)
        // 15=3*5(5*3)、16=2*8、18=2*9(3*6)、20=2*10(5*4)、24=2*12(3*8)、25=5*5、27=3*9、30=2*15(3*10\5*6)
        // 32=2*16、36=2*18(3*12)、40=2*20(5*8)、45=5*9(3*15)、48=2*24(3*16)、50=2*25(5*10)、54=2*27(3*18)、60=2*30(3*20\5*12)
        // 64=2*32、72=2*36(3*24)、75=3*25(5*15)、80=2*40(5*16)、81=3*27、90=2*45(3*30\5*18)、96=2*48(3*32)、100=2*50(5*20)
        int[] result = new int[index];
        result[0] = 1;
        int flag2 = 0;
        int flag3 = 0;
        int flag5 = 0;

        for (int i = 1; i < result.length; i++) {
            int prod2 = result[flag2] * 2;
            int prod3 = result[flag3] * 3;
            int prod5 = result[flag5] * 5;
            int min = (prod2 < prod3) ? prod2 : prod3;
            min = (min < prod5) ? min : prod5;

            result[i] = min;
            if (prod2 <= min) {
                flag2++;
            }
            if (prod3 <= min) {
                flag3++;
            }
            if (prod5 <= min) {
                flag5++;
            }
        }

        return result[index - 1];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.GetUglyNumber_Solution(12));
    }
}
